/*************************************************************************
 * File Name:    PathSum_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/4 9:33:42
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Path Sum II
 |
 | Given a binary tree and a sum, find all root-to-leaf paths where
 | each path's sum equals the given sum.
 |
 | For example:
 | Given the below binary tree and sum = 22,
 |            5
 |           / \
 |          4   8
 |         /   / \
 |        11  13  4
 |       /  \    / \
 |      7    2  5   1
 | return
 | [
 |   [5,4,11,2],
 |   [5,8,4,5]
 | ]
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > pathSum(TreeNode *root, int sum)
    {
        vector<vector<int> > ans;
        
        if (root == NULL) return ans;
        vector<int> path;
        
        dfs(root, sum, path, ans);
        return ans;
    }

    void dfs(TreeNode *root, int sum, vector<int> &path, vector<vector<int> > &ans)
    {
        sum -= root->val;
        path.push_back(root->val);
        
        if (root->left == NULL && root->right == NULL && sum == 0) {
            ans.push_back(path);
        }
        if (root->left != NULL) dfs(root->left, sum, path, ans);
        if (root->right != NULL) dfs(root->right, sum, path, ans);
        path.pop_back();
    }
};

